package leetcode.code0424;



import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int characterReplacement(String s, int k) {
		// "ADAAACBADDCBCCBA"
		int[] dics = new int[26];// 窗口中a,b的大小
		int ans = 0, max = 0, size = 0, rest = 0;// 答案长度
		int l = 0, r = 0;// 窗口左右
		char[] cs = s.toCharArray();
		int len = cs.length;
		while (r < len) {
			int cur = cs[r] - 'A';
			dics[cur]++;
			max = Math.max(max, dics[cur]);
			size = r - l + 1;
			rest = size - max;
			if (rest <= k) {
				ans = Math.max(ans, size);
			} else {
				do {
					dics[cs[l++] - 'A']--;
					max = 0;
					for (int i = 0; i < 26; i++) {
						max = Math.max(max, dics[i]);
					}
				} while (r - l + 1 - max > k);
			}
			r++;
		}
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(6, this.characterReplacement("ADAAACBADDCBCCBA", 2));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

		HelpDebug.compare(4, this.characterReplacement("ABAB", 2));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		HelpDebug.compare(4, this.characterReplacement("AABABBA", 1));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug2();
		so.debug1();
		so.debug3();
		so.debug4();

	}

}
